This invention relates to, for example, an implementation for the Nationwide Health Information Exchange (NwHIN). The NwHIN is a ‘network of networks’ for exchanging health data. The fabric of the NwHIN is based on web services that provide the framework among NwHIN participants to locate and exchange health information. Examples of NwHIN participants currently include: state level exchanges, IDNs, federal entities, public health entities, and geographically-based health information organizations. In order to qualify as an NwHIN participant, the Health Information Organization (HIO) must receive NwHIN Validation, which includes conformance and compliance testing. When an NwHIN member is asked for medical records, they need to know the identity of the individual for whom the records are being requested. But every organization could have a different identifier for the patients they see. Organization A may keep records by Social Security Number (SSN), while Organization B might keep them by some internally generated patient ID.